package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/6/30
 * Description:
 * - 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 * <p>
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 **/
public class Que5 {

    public static void main(String[] args) {
        System.out.println(new Solution().longestPalindrome("a"));
    }

    static class Solution {

        public String longestPalindrome(String s) {
            // 长度、起始位置
            int len = 0;
            int idx = 0;

            for (int i = 0; i < s.length(); i++) {
                int l = check(s, i, i);
                if (2 * l + 1 > len) {
                    len = 2 * l + 1;
                    idx = i - l;
                }

                l = check(s, i, i + 1);
                if (2 * l > len) {
                    len = 2 * l;
                    idx = i - (l - 1);
                }
            }
            return s.substring(idx, idx + len);
        }

        private static int check(String s, int i, int j) {
            while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            }
            return (j - (++i)) / 2;
        }
    }

    static class Solution1 {

        public String longestPalindrome(String s) {
            // 长度、起始位置
            int[] res = new int[]{0, 0};

            for (int i = 0; i < s.length(); i++) {
                check(s, i, i, res);
                check(s, i, i + 1, res);
            }

            return s.substring(res[1], res[1] + res[0]);
        }

        private static void check(String s, int i, int j, int[] res) {
            while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            }
            if (j - (++i) <= res[0]) return;

            res[0] = j - i;
            res[1] = i;
        }
    }
}
